/**
 * 303. Range Sum Query - Immutable
 * https://leetcode.com/problems/range-sum-query-immutable/description/
 *
 * @author Kevin
 * @date 2018-12-25
 */
public class NumArray2 {

    /**
     * 求和数列
     * <p>
     * 思路：
     * sum[i]存储前i个元素和, sum[0] = 0
     * 即sum[i]存储nums[0...i-1]的和
     * sum(i, j) = sum[j + 1] - sum[i]
     */
    private int[] sum;

    public NumArray2(int[] nums) {
        this.sum = new int[nums.length + 1];
        this.sum[0] = 0;
        for (int i = 1; i < this.sum.length; i++) {
            this.sum[i] = this.sum[i - 1] + nums[i - 1];
        }
    }

    /**
     * 求区间内的和
     *
     * @param i
     * @param j
     * @return
     */
    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }

    public static void main(String[] args) {
        int[] nums = {-2, 0, 3, -5, 2, -1};
        NumArray2 numArray = new NumArray2(nums);
        System.out.println(numArray.sumRange(0, 2));
        System.out.println(numArray.sumRange(2, 5));
        System.out.println(numArray.sumRange(0, 5));
    }

}
